Existing software applications allow users to animate electronic characters and other artwork by placing a few handles on the artwork and then moving these handles. The software then figures out how to smoothly deform the rest of the artwork based on the handle movements. In this way, a user is able to animate the artwork by controlling only a few simple parameters, i.e., moving the handles.
Deforming the artwork based on the movement of the handles is accomplished by associating the handles with the rest of the artwork using a mesh of triangles with vertices (on the artwork) that are weighted relative to the handles. For each handle, an affine transformation is determined. The affine transformation is a geometric transformation that maps variables (e.g., pixel intensity values located at positions (x1, y1) in an image) into new variables (e.g., (x2, y2) in an output image) by applying a linear combination of translation, rotation, scaling, and/or shearing operations. Transformations for the vertices of the mesh are determined based on the weighted blending of the handle affine transformations. The handle affine transformations are thus used to determine how the mesh changes.
One existing deformation approach determines handle affine transformations by using an “as rigid as possible” technique that attempts to ensure that every small piece of the mesh deforms in a way that is as rigid as possible, i.e., to avoid stretching and squashing as much as possible in small portions of the mesh. The technique does so by breaking the mesh up into rotation clusters (groups of vertices) that it attempts to keep as rigid as possible (with minimal stretching and squashing) in a local/global iterative process. The local step solves for an optimal rigid transformation for each rotation cluster using a singular value decomposition in each iteration. The global step solves a linear system of rotational, scaling and shearing parameters for each handle while holding the rotations for each cluster fixed. Although this alternating local/global deformation algorithm is formulated to be efficiently solvable, it can sometimes be too slow for smooth real-time deformations, particularly when implemented on mobile devices.